#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

   struct node
 {
   int data;
   struct node *next;
 }*p;
int o=0;



//1 & 2
void append( int num )
 {
     struct node *temp,*r;
     o++;
       temp= malloc(sizeof(struct node));
       temp->data=num;
       r=p;

      if (p == NULL) 
     {
         p=temp;
         p->next =NULL;
     }
  else
     {        

       while( r->next != NULL)
                r=r->next;
       r->next =temp;
       r=temp;
       r->next=NULL;
     }
  }




//3

insertion(int num, int number)
  {
        o++;
     int i;
     struct node *temp,*t,*r;
     r=p;
        if (number == 1)
         {
           struct node *temp;
        temp=malloc(sizeof(struct node));
        temp->data=num;
        if ( p== NULL)
         {
          p=temp;
          p->next=NULL;
         }
        else
        {
         temp->next=p;
         p=temp;
        }
           return 0;
         }
      else
        {
       for(i=1;i<number;i++)
          {
             t=r;   
             r=r->next;
          }
         temp=malloc(sizeof(struct node));
         temp->data=num;
         t->next=temp;
         t=temp;
         t->next=r;
        return 0;
       }
}


//4

 int delete1(int num)
 {
     struct node *temp, *m;
temp=p;
      while(temp!=NULL)
    {
       if(temp->data==num)
       {
           if(temp==p)
           {
              p=temp->next;
              free(temp);
              o--;
              return 0;
           }
           else
         {
           m->next=temp->next;
           free(temp);
           o--;
           return 0;
         }
      }else
        {
          m=temp;
          temp= temp->next;
        }

}
    printf("ELEMENT %d NOT FOUND ", num);

}

//5
int pop(int ind)
{
int x,i;
struct node *d,*temp;
d=p;
        if(ind==1)
   {    temp=p;
        p=temp->next;
        x=temp->data;
        free(temp);                                         
        return x;
     
}
        else if(ind==o-1)
        {
        for(i=1;i<o+1;i++)
        d=d->next;
        temp=d->next;
        x=temp->data;
        free(temp->next);               
        d->next=NULL;
        return x;
        }




        else
        {
        for(i=1;i<ind-1;i++)
        d=d->next;
        
        temp=d->next;
        x=temp->data;
        d->next=temp->next;

        free(temp);
        
        return x;
        }
}





//6
int index1(int number)
      {
      int c=1;
      int flag=0;
      struct node *d;
      d=p;
      if(d==NULL)
      {
      printf("List is empty");
      return -2;
      }
       while(d!=NULL)
      {
      if(d->data==number)
        {
        
        flag=1;
        break;
        }
      else
        {
        d=d->next;
        c++;
        }
        }
        if(flag==0){
        printf("Number is not in the list");
        return 0;
        }
        else
        return c;
        }

        


//7
int count1(int number)
      {
      int c=0;
      struct node *d;
      d=p;
      if(d==NULL)
      {
      printf("List is empty");
      return -1;
      }
       while(d!=NULL)
      {
      if(d->data==number)
        {
        c=c+1;
        d=d->next;
        }
      else
        {
        d=d->next;
        }
        }
        return c;
        }


       


//8

void reverse(struct node *q)
{
   struct node *x, *y,*l,*s;
   x=q;
   y=NULL;
  while(x!=NULL)
 {
   s=y;
   y=x;
   x=x->next;
   y->next=s;
 }
   p=y;
}

//for sort function taken help from internet 
void sort(void) {
struct node *a = NULL;
struct node *b = NULL;
struct node *c = NULL;
struct node *e = NULL;
struct node *tmp = NULL;
while(e != p->next)
{
c = a = p;
b = a->next;
while(a != e)
{
if(a->data > b->data)
{
if(a == p)
{
tmp = b -> next;
b->next = a;
a->next = tmp;
p = b;
c = b;
} else {
tmp = b->next;
b->next = a;
a->next = tmp;
c->next = b;
c = b;
}
} else
{
c = a;
a = a->next;
}
b = a->next;
if(b == e)
e = a;
}
}
} 

void sort1(){
	sort();
	reverse(p);
}
//10
void display(struct node *x)
  {
      x=p;
      if(x==NULL)
     {
       printf("NO ELEMENT IN THE LIST :");
       return;
     }
       while(x!=NULL)
    {
      printf(" %d \t",x->data);
      x=x->next;
    }
  }








  main()
 {
        int i;
   p=NULL;
   while(1) 
        {
    printf("\n1.To append the list \n2.To extend the list\n3.To insert a number as specific position in a list \n4.To remove from a list\n5.To pop a element from list \n6.To return the index of number in the list\n7.To count the number of occurance of a number in list \n8.To reverse a list \n9.To sort the list \n10.To display the list \n0.To exit\n");
    scanf("%d",&i);


      switch(i)
    {
         case 1:
      {
        int num;
        printf("Enter the number");
        scanf("%d",&num);
        append(num);
        break;
      }

        case 2:
        {
          int num,n;
          printf("Enter the size of list of number u want to append \n");
          scanf("%d",&n);
                for(i=0;i<n;i++)
                {
                        printf("Enter the number \n");
                        scanf("%d",&num);
                        append(num);
                }
                break;
        }
   case 3:
     {

      int num, number,h;
      printf("Enter the number");
      scanf("%d",&num);
      printf("Enter the position ");
      scanf("%d",&number);
	if(number<=o+1){
      insertion(num,number);
      break;
}
	else
	{
	printf("invalid");
	break;
	} 
}
    
  case 4:
    {
      int num;
      printf("Enter the number which has to be deleted :");
      scanf(" %d",&num);
      delete1(num);
     break;
    }
        case 5:
         {
                int h,y;
                
                printf("Enter the position at which u want to delete(Enter -1 if u do want to specify the position) \n");
                scanf(" %d",&h);
                if(h<o+1)
                {
                if(h==-1)
                        y=pop(o);
                else
                        y=pop(h);
                printf("Element being deleted is %d",y);
                }
                else
                printf("ERROR Index does not Exist");
                break;
                  }
        
        

   case 6:
     {
     int num;
        int x;
        printf("Enter the number whose index has to be find");
        scanf(" %d",&num);
        x=index1(num);
        if(x>0)
        printf("index of the number is %d",x);

        break; 
        }
   case 7:      
        {
        int num;
        int x;
        printf("Enter the number whose occurance has to be find");
        scanf(" %d",&num);
        x=count1(num);
        if(x==0)
        printf("Number is not in list");
        else
        printf("Occurance of the number is %d",x);
        break; 
        }
   


  case 8:
    {
      reverse(p);
        break;
    }
	

 case 9:
	 {
		int m;
		printf("enter 0 for acending order and 1 for descending \n");
		scanf(" %d",&m);
		if(m==1)
		sort();
		else
		sort1();
		reverse(p);
		break;
	 }
case 10:
      {
         struct node *n;
         printf("Elements in the list are ");
         display(n);
         break;
      }

  case 0:
 {
  exit(1);
 }
    }/* end if switch */
 }/* end of while */
}/* end of main */

